package com.gjx.leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

//107. 二叉树的层次遍历 II
//
//给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
//
//例如：
//给定二叉树 [3,9,20,null,null,15,7],
//
//    3
//   / \
//  9  20
//    /  \
//   15   7
//返回其自底向上的层次遍历为：
//
//[
//  [15,7],
//  [9,20],
//  [3]
//]




public class Solution107 {
	public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res = new LinkedList<>();
        if (root == null) {
        	return res;
        }
        
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        
        while (!q.isEmpty()) {
        	
        	int size = q.size();
        	
        	List<Integer> list = new ArrayList<>();
        	
        	for (int i=0; i<size; i++) {
        		
        		TreeNode tn = q.poll();
        		list.add(tn.val);
        		
        		if (tn.left != null) q.offer(tn.left);
        		if (tn.right != null) q.offer(tn.right);
        		
        	}
        	
        	res.add(0, list);
        	
        	
        }
        
        return res;
    }
}
